package lc.q300_350;

import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 给你一个数组 nums ，请你完成两类查询。
 *
 * 其中一类查询要求 更新 数组 nums 下标对应的值
 * 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right
 * 实现 NumArray 类：
 *
 * NumArray(int[] nums) 用整数数组 nums 初始化对象
 * void update(int index, int val) 将 nums[index] 的值 更新 为 val
 * int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）
 */
public class Q307 {

    public static void main(String[] args) {
        NumArray numArray = new NumArray(new int[]{1, 3, 5});
        System.out.println(numArray.sumRange(0,2));
        numArray.update(1,2);
        System.out.println(numArray.sumRange(0,2));
    }

    // 线段树？
    public static class NumArray2 {

        /**
         * 线段树 segmentTree 是一个二叉树，
         * 每个结点保存数组 nums 在区间 [s,e] 的最小值、最大值或者总和等信息。
         * 线段树可以用树也可以用数组（堆式存储）来实现。对于数组实现，假设根结点的下标为 0，
         * 如果一个结点在数组的下标为 node，那么它的左子结点下标为 node×2+1，右子结点下标为 node×2+2。
         *
         * 作者：力扣官方题解
         * 链接：https://leetcode.cn/problems/range-sum-query-mutable/solutions/1389182/qu-yu-he-jian-suo-shu-zu-ke-xiu-gai-by-l-76xj/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         */

        int[] nums;

        int[] tree;
        int n;

        public NumArray2(int[] nums) {
            this.n = nums.length;
            this.nums = nums;
            // 构造树
            this.tree = new int[n * 4];
            buildTree(0, 0, n - 1, nums);
        }

        private void buildTree(int node, int s, int e, int[] nums) {
            if (s == e) {
                tree[node] = nums[s];
                return;
            }
            // 构造左边
            int m = s + (e - s) / 2;
            buildTree(node * 2 + 1, s, m, nums);
            buildTree(node * 2 + 2, m + 1, e, nums);
            tree[node] = tree[node * 2 + 2] + tree[node * 2 + 1];
        }

        private void change(int index, int val, int node, int s, int e) {
            // 修改树
            if (s == e) {
                tree[node] = val;
                return;
            }
            int m = s + (e - s) / 2;
            if (index < m) {
                // 修改左边
                change(index, val, node * 2 + 1, s, m);
            } else {
                // 修改右边
                change(index, val, node * 2 + 2, m + 1, e);
            }
            tree[node] = tree[node * 2 + 2] + tree[node * 2 + 1];
        }

        public void update(int index, int val) {
            this.nums[index] = val;
            // 从第根节点修改起
            change(index, val, 0, 0, n - 1);
        }

        public int sumRange(int left, int right) {
            return 0;
        }

        private int range(int left, int right, int node, int s, int e) {
            if (left == s && right == e) {
                return tree[node];
            }
            int m = s + (e - s) / 2;
            if (right <= m) {
                // 说明在答案在左边
                return range(left, right, node * 2 + 1, s, m);
            } else if (left > m) {
                // 说明答案在右边
                return range(left, right, node * 2 + 2, m + 1, e);
            } else {
                //
                return range(left, m, node * 2 + 1, s, m) +
                        range(m + 1, right, node * 2 + 2, m + 1, e);

            }
        }
    }


    public static class NumArray {

        private int[] nums;
        private int[] sums;// 这里存分段的和

        private int size;


        public NumArray(int[] nums) {
            this.nums = nums;
            // 求分段和
            this.size = (int) Math.sqrt(nums.length);
            this.sums = new int[(nums.length + size - 1) / size]; // 向上取整
            for (int i = 0; i < sums.length; i++) {
                int sum = 0;
                for (int j = i * size; j < i * size + size && j < nums.length; j++) {
                    sum += nums[j];
                }
                sums[i] = sum;
            }
        }

        public void update(int index, int val) {
            // 调整对应段的和
            int orgVal = nums[index];
            this.nums[index] = val;
            int part = index / size;
            sums[part] += (val - orgVal);
        }



        public int sumRange(int left, int right) {
            // 计算left的part部分到right的部分
            int leftPart = left / size;
            int rightPart = right / size;
            int sum = 0;
            for (int i = leftPart; i < rightPart; i++) {
                sum += sums[i];
            }
            // 减去多的部分
            int leftRemain = left % size;
            for (int i = 0; i < leftRemain; i++) {
                sum -= nums[i + leftPart * size];
            }
            int rightRemain = right % size;
            // 加上right前半部分
            for (int i = 0; i <= rightRemain && (i + rightPart * size) < nums.length; i++) {
                sum += nums[i + rightPart * size];
            }
            return sum;
        }
    }
}
